package leetcode.hot100;

import java.util.ArrayList;
import java.util.List;

@SuppressWarnings("all")
public class _22_括号生成_dfs {

    // 数字 n 代表生成括号的对数，这 n 对括号排列组合能够生成多少对有效的括号组合
    int n;
    List<String> resultList;

    public List<String> generateParenthesis(int n) {
        this.n = n;
        this.resultList = new ArrayList<>();
        help("", 0, 0);
        return resultList;
    }

    /**
     * @param cur   当前的括号组合
     * @param left  左括号数量
     * @param right 右括号数量
     */
    private void help(String cur, int left, int right) {
        if (left == n && right == n) {
            resultList.add(cur);
            return;
        }
        // 剪枝：当左括号数量已经大于给定的数量或者右括号更多时，说明已经不能满足有效的括号组合了
        if (left > n || left < right) return;
        // 找下一个组合，左括号数量加1
        help(cur + "(", left + 1, right);
        // 找下一个组合，右括号数量加1
        help(cur + ")", left, right + 1);
    }


    // 动态规划的思想类似于数学归纳法，当知道所有 i<n 的情况时，我们可以通过某种算法算出 i=n 的情况
    // 本题最核心的思想是，考虑 i=n 时相比 n-1 组括号增加的那一组括号的位置
}